{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "leetcode 42.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gD221bs84X8T"
      },
      "source": [
        "dynamic programming, time O(n), space O(n)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UnZ1EZN226jL"
      },
      "source": [
        "class Solution:\n",
        "    def trap(self, height):\n",
        "        \n",
        "        ret = 0 \n",
        "        \n",
        "        # check input \n",
        "        if len(height) == 0:\n",
        "            return ret  \n",
        "        \n",
        "        left_max = [0] * len(height)\n",
        "        right_max = [0] * len(height)\n",
        "        \n",
        "        for i in range(len(height)):\n",
        "            if i == 0:\n",
        "                left_max[i] = height[i]\n",
        "            else:\n",
        "                left_max[i] = max(left_max[i-1], height[i])\n",
        "\n",
        "        for i in range(len(height) - 1, -1, -1):\n",
        "            if i == len(height) - 1:\n",
        "                right_max[i] = height[i]\n",
        "            else:\n",
        "                right_max[i] = max(right_max[i+1], height[i])\n",
        "        \n",
        "        for i in range(len(height)):\n",
        "            ret += (min(left_max[i], right_max[i]) - height[i])\n",
        "\n",
        "        return ret "
      ],
      "execution_count": 25,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "m0A9_tk-29Ys",
        "outputId": "9f84426b-5e64-4415-d261-356d79f35030",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "s = Solution()\n",
        "input = [0,1,0,2]\n",
        "print(s.trap(input))"
      ],
      "execution_count": 26,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}